package com.zzg.datastructure.linkedlist;

import java.util.Stack;

/**
 * @Author zhengzg
 * @Date 2022-08-16
 * @Version v1.0
 */
public class SingleLinkedList {

    // 先初始化一个头节点，头节点不能动，不存放具体数据
    private final HeroNode head = new HeroNode(0,"","");

    public HeroNode getHead() {
        return head;
    }

    // 第一种：添加节点到单向链表
    /*
     * 思路：不考虑编号顺序时
     * 1. 找到当前链表的最后节点
     * 2. 将最后这个节点的next指向新的节点
     */
    public void add(HeroNode heroNode){
        // 头节点不能动，增加辅助遍历temp
        HeroNode temp = head;
        //遍历链表找到最后的前一个
        while (temp.next != null) {
            // 如果没有找到，就将temp后移
            temp = temp.next;
        }

        // 退出while时，temp指向链表最后
        // 将最后这个节点的next指向新的节点
        temp.next = heroNode;
    }

    // 第二种：根据排名将英雄插入指定的位置
    public void addByOrder(HeroNode heroNode){
        HeroNode temp = head;

        // 标志：判断添加的英雄编号是否存在
        boolean flag = false;

        while (true){
            // 到达链表最后
            if (temp.next == null){
                break;
            }

            // temp后一个节点编号大于插入英雄的编号，在temp后方插入
            if (temp.next.no > heroNode.no){
                break;
            } else if (temp.next.no == heroNode.no){
                // 编号已经存在
                flag = true;
                break;
            }
            //将temp后移
            temp = temp.next;
        }

        // 判断flag的值
        if (flag){
            System.out.printf("准备插入的英雄的编号 %d 已经存在，不能加入\n",heroNode.no);
        } else {
            // 插入到链表中，temp的后面
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }

    // 修改节点信息，根据no编号来修改
    public void update(HeroNode newHeroNode){
        // 判断是否null
        if(head.next == null){
            System.out.println("链表为空——");
            return;
        }
        HeroNode temp = head.next;

        // 表示是否可以找到节点
        boolean flag = false;
        while (true){
            if (temp == null){
                break;
            }
            if (temp.no == newHeroNode.no){
                flag = true;
                break;
            }
            // 没有找到继续寻找下一个节点
            temp = temp.next;
        }

        // 根据flag判断是否找到要修改的节点
        if (flag){
            temp.name = newHeroNode.name;
            temp.nickName = newHeroNode.nickName;
        } else {
            System.out.println("该节点不存在");
        }
    }

    // 删除节点
    public  void del(int no){
        HeroNode temp = head.next;
        // 标志待删除的节点是否存在
        boolean flag = false;
        while (true){
            if (temp == null){
                // 找到最后没有
                break;
            }

            if (temp.next.no == no){
                // 找到要删除节点的前一个节点
                flag = true;
                break;
            }
            // 让节点向后移动
            temp = temp.next;
        }

        if (flag){
            temp.next = temp.next.next;
        } else {
            System.out.println("节点不存在");
        }
    }

    // 显示链表【遍历】
    public void list(){
        if (head.next == null){
            System.out.println("链表为null");
            return;
        }

        HeroNode temp = head.next;

        while (true) {
            // 输出节点信息
            System.out.println(temp);

            if (temp.next == null){
                break;
            }
            // 将temp后移
            temp = temp.next;
        }
    }

    /**
     * 获取单链表中节点个数（如果是带头节点的，需求不统计头节点）
     * @param heroNode 头节点
     * @return 节点个数
     */
    public static int getLength(HeroNode heroNode){
        if (heroNode.next == null){
            return 0;
        }

        int length = 0;

        // 定义一个辅助的变量，这里没有统计头节点
        HeroNode cur = heroNode.next;
        while (true){
            length++;
            // 因为cur的next可能为null，需要进行处理
            if (cur.next == null){
                break;
            }
            // 继续遍历下一个节点
            cur = cur.next;
        }
        return length;
    }

    /**
     * 新浪面试题 ------> 查找单链表中的倒数第k个节点
     * 1. 编写方案接收head节点，同时接收一个index
     * 2. index 表示的是倒数第index个节点
     * 3. 先把链表从头到尾遍历，得到链表的总的长度 getLength
     * 4. 得到size后，我们从链表的第一个开始遍历（size - index）个，就可以得到
     * 5. 如果找到，则返回该节点，否则返回null
     */
    public static HeroNode findLastIndexNode(HeroNode head,int index){
        if (head.next == null){
            System.out.println("链表为null");
            return null;
        }

        // 得到链表总长度
        int size = getLength(head);

        // 判断index是否合法
        if (index <= 0 || index > size){
            return null;
        }

        // 定义辅助变量
        HeroNode cur = head.next;
        // 找后第k个数据，相当于从前查size - k + 1个数据
        for (int i = 0; i < size - index; i++) {
            cur = cur.next;
        }

        return cur;

    }

    /**
     * 腾讯面试题 -------------------> 单链表的反转
     * 1. 先定义一个新的单链表头节点
     * 2.从头到尾遍历原来的链表，每遍历一个节点，就将其取出，放在新头节点的后面
     * 3，遍历完成之后将旧的头节点next指向新头节点的next
     * 注：会改变原链表
     */
    public static void reversetList(HeroNode head){
        // 判断链表是否为null
        if (head.next == null || head.next.next == null){
            // 链表为null或者只有一个数据，反转无意义
            return;
        }

        // 辅助变量
        HeroNode cur = head.next;
        // 指向当前节点的下一个节点
        HeroNode next = null;
        // 新头节点
        HeroNode newHead = new HeroNode(0, "", "");

        // 遍历原来链表
        while (cur != null){
            // 保存当前节点的下一个节点
            next = cur.next;
            // 将cur的next节点指向 新链表的最前端
            // 反转，就相当于将原链表第一个数据放到最后，那么原链表第一个节点就应该指向新链表的null节点，以此类推
            cur.next = newHead.next;
            // 把cur节点的数连接到新链表中
            newHead.next = cur;
            // 让cur后移
            cur = next;
        }

        // 将head.next 指向 newHead.next 实现反转
        head.next = newHead.next;
    }

    /**
     * 百度面试题  ------------------------> 从头到尾打印单链表，要求反向遍历
     * 1. 使用栈操作
     */

    public static void reversetPrint(HeroNode head){
        if (head.next == null){
            System.out.println("链表数据为null");
            return;
        }

        // 创建一个栈，将各个节点压入栈
        Stack<HeroNode> stack = new Stack<>();

        HeroNode cur = head.next;

        // 将链表所有节点入栈
        while (true){
            stack.push(cur);
            if (cur.next == null){
                break;
            }
            // 将节点后移
            cur = cur.next;
        }

        // 将栈中节点进行打印出栈
        while (stack.size() > 0){
            System.out.println(stack.pop());
        }
    }
}
